倍增算法

倍增,顾名思义,就是成倍成倍的增加. 每次都在前一次的基础上增加一倍,这个过程就是倍增.
倍增在处理dp,序列搜索,最近公共祖先等问题时非常有效.在一些能快速推导出递推关系的问题中,常常可以
通过倍增的方法将原本线性或平方级别的复杂度优化到对数级别.

#include<bits/stdc++.h>
using namespace std;

int a[100010],f[100010][21];  // 一维是数据 二维用于存储状态
int n,m;
void pre(){
    // 1. 预处理  所有可能情况进行推导并存储.
    for(int i = 1; i <= n; i++){
        f[i][0] = a[i];  // 走2^0步后到达自身位置
    }
    // 2. 询问阶段 根据预处理的结果进行推导. 
    for(int j = 1; j <= 20; j++){
        for(int i = 1; i <= n - (1 << j) + 1; i++){
            f[i][j] = f[f[i][j - 1]][j - 1];  // f[i][j]表示从i走2^j步到达的位置
        }
    }
}

int main(){
    
    return 0;
}